Le mappature matematiche e la modellazione dei dati fungono da ponte tra la teoria degli insiemi astratta e la realtà computazionale. All'interno di questo quadro, un algoritmo agisce come una trasformazione formale e deterministica in cui l'input strutturato viene elaborato attraverso istruzioni precise per produrre un output corretto. Questo stabilisce la base logica per tutto il software e l'architettura dei database.
Le Proprietà di un Algoritmo
Un algoritmo è un metodo passo-passo per risolvere un problema, caratterizzato da sette pilastri fondamentali:
- Input: L'algoritmo riceve dati da un insieme specificato.
- Output: L'algoritmo produce un risultato (la soluzione) da un insieme specificato.
- Precisione: Ogni passaggio è enunciato con chiarezza assoluta.
- Determinismo: I risultati intermedi sono unici e dipendono esclusivamente dagli input e dai passaggi precedenti.
- Finitudine: Il processo termina dopo un numero finito di istruzioni.
- Correttezza: L'output risolve il problema come previsto.
- Generalità: La procedura si applica a una classe intera di input, non solo a un singolo caso.
Algoritmo 4.1.1: Trovare il Massimo di Tre Numeri
Questa semplice relazione ternaria dimostra precisione e determinismo. Indipendentemente dai valori di $a, b,$ e $c$, i passaggi seguono un percorso logico rigido.
Traccia del Pseudocodice
max3(a, b, c) {
grande = a
se (b > grande) grande = b
se (c > grande) grande = c
ritorna grande
}Modellazione dei Dati e Invarianti di Ciclo
In strutture dati più complesse, come le sequenze ($s_1, ..., s_n$), utilizziamo Algoritmo 4.1.2. Per garantire che tali algoritmi siano corretti, ci basiamo sull'induzione e sul concetto di invariante di ciclo.
Algoritmo 4.1.2: Trovare il Massimo in una Sequenza
max(s, n) {
grande = s_1
per i = 2 a n
se (s_i > grande)
grande = s_i
ritorna grande
}Invariante di Ciclo: "grande è il valore più grande nella sotto-sequenza $s_1, ..., s_i$". Questa proprietà rimane vera in ogni iterazione, dimostrando la correttezza per induzione.
🎯 Principio Fondamentale: Validità della Mappatura
Una funzione matematica valida richiede che ogni elemento nel dominio si mappi in esattamente uno elemento nel codominio. La mancanza di frecce o frecce multiple da una sola fonte invalida lo stato di funzione, riflettendo perché gli algoritmi non deterministici o incompleti falliscono nella pratica.